Traffic demands in transport networks (e.g., mobile backhaul networks) are time-varying and, typically, the traffic load variations are reappearing following certain patterns. For example, as shown in FIG. 1, the traffic demands of cellular backhaul networks in residential areas (FIG. 1a) and in commercial areas (FIG. 1b) change over time during one typical working day and this variation is usually repeated following the same pattern on every working day (for reference see, for instance, Juha Salmelin, and Esa Metsälä, “Mobile Backhaul,” John Wiley & Sons, May, 2012).
Such time-varying traffic demands can be characterized with multiple traffic demand matrices of different time slots during one day. The multiple traffic matrices can be obtained based on historic data and/or traffic prediction from statistical traffic models. Tab. I and Tab. II below show two sample traffic matrices for a number of routers Ri for two different quality-of-service (QoS) classes in an n-th time slot. Generally, the network traffic may be categorized into a hierarchy of traffic classes (i.e., differentiated services specified by different QoS requirements).
TABLE IExample of traffic matrix in nth time slot - QoS class #1.ToFromR1R2R3R4R5R6R1——15 Mbps30 Mbps45 Mbps—R220 Mbps55 Mbps30 Mbps——10 MbpsR3———35 Mbps25 Mbps—R415 Mbps40 Mbps40 Mbps——30 MbpsR525 Mbps35 Mbps—30 Mbps——R630 Mbps—55 Mbps—35 Mbps—
TABLE IIExample of traffic matrix in nth time slot - QoS class #2.ToFromR1R2R3R4R5R6R1——25 Mbps50 Mbps70 Mbps—R230 Mbps—50 Mbps——15 MbpsR3———30 Mbps60 Mbps—R420 Mbps30 Mbps20 Mbps——20 MbpsR515 Mbps25 Mbps—40 Mbps——R670 Mbps—45 Mbps—30 Mbps40 Mbps
To accommodate the multiple traffic matrices of different time slots in transport networks, time-dependent (re)routing schemes are adopted in practice. FIGS. 2 and 3 together show an example of time-dependent (re)routing for a single source-destination pair, with router R1 being the source node and router R2 being the destination note. When there are multiple source-destination pairs (as is the case, for example, in realistic mobile networks), the routing paths established for most of the source-destination pairs have to be changed (re-configured) across different time slots. This is called Bulk Rerouting, as a bulk of traffic demands (e.g., a bulk of VLANs) are rerouted across different time slots.
While time-dependent routing achieves increased link utilization and network throughput under time-varying traffic demands, the re-provisioning of the routing paths to the routers and switches across different time slots may take too much time and may incur too much signaling overhead and therefore cause significant service disruptions (for reference see, for instance, Jean-Philippe Vasseur, Mario Pickavet, and Piet Demeester: “Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS” in Morgan Kaufmann Publishers Inc., August, 2004). To minimize the transition impact, which can be measured in terms of packet loss, jitter, video quality degradation, etc., bulk rerouting shall be carried out in a pre-scheduled manner. That is, all the time-dependent routing paths of different time slots are pre-configured and pre-provisioned to the routers/switches, and the bulk rerouting is performed according to the pre-established schedule (e.g., a pre-established time-dependent routing table).
When the network nodes are perfectly synchronized, bulk rerouting can be carried out at the boundaries of different time slots in an atomic way. That is, when the network is perfectly synchronized, the traffic between multiple source-destination pairs can be switched to new paths simultaneously at the boundaries of different time slots, according to the pre-established bulk rerouting schedules, e.g., time-dependent routing tables (for reference see, for instance, Y. Watanabe, and T. Oda: “Dynamic routing schemes for international networks”, in IEEE Communications Magazine, vol. 28, no. 10, pp. 70-75, October 1990).
In reality, however, the network nodes (e.g., gateways, routers, switches, etc.) are not perfectly synchronized. For example, even with the Precision Time Protocol (PTP) as specified in the standard IEEE 1588v2 (for reference see, Jean-Loup Ferrant, and Mike Gilson, et. al. “Synchronous Ethernet and IEEE 1588 in Telecoms: Next Generation Synchronization Networks,” John Wiley & Sons, June, 2013, as well as Symmetricom: “Synchronization for Next Generation Networks—The PTP Telecom Profile,” White Paper, 2011), accuracy of network synchronization will typically be in the order of a few microseconds (μs). With a transmission rate (line speed) of 100 Gbps, a mere 1 μs difference in timing between two network nodes may cause the loss (or misrouting or out of order delivery) of about 100 of kilobits traffic for one source-destination pair alone.
In summary, in practical transport networks with imperfect network synchronization, bulk rerouting cannot be performed in an atomic way without incurring packet loss. One way to address this problem is by carefully sequencing the switch-over of services to their new configuration one by one. However, this can become difficult if the network is close to saturation, since in such case there will be a chicken-and-egg problem of freeing resources first before other services can be rerouted.